package 删除链表的倒数第N个节点;


class Solution {

    // 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 快慢指针的方法
        // 刚开始的时候fast指针比slow指针多走n步，然后fast和slow指针同时往后走，当fast.next为null的时候，slow指针指向的就是倒数第n个节点的前驱节点
        /*
            链表中结点的数目为 sz
            1 <= sz <= 30
            0 <= Node.val <= 100
            1 <= n <= sz
         */

        // 虚拟头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode slow = dummyNode;
        ListNode fast = dummyNode;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 此时 slow和fast 指针相距n个节点
        while ( fast.next != null ){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummyNode.next;
    }

}